import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class J092602 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public static List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            while (cur != null || !stack.isEmpty()) {
                list.add(cur.val);
                TreeNode left = cur.left;
                TreeNode right = cur.right;
                if (right != null) {
                    stack.push(right);
                }
                if (left != null) {
                    stack.push(left);
                }
                if(! stack.isEmpty()){
                    cur = stack.pop();
                }else{
                    cur = null;
                }
            }
            return list;
        }

        public static void main(String[] args) {
            TreeNode root = new TreeNode(1);
            root.right = new TreeNode(2);
            root.right.left = new TreeNode(3);
            List<Integer> lastTree = preorderTraversal(root);
            System.out.println(lastTree.toString());
        }
    }
}
